//Cracking coding interviews 10.5
//Pring string
//6:44PM--7:04PM--7:08PM(bug free)


#include<iostream>
using namespace std;

int LookUp(char *input[], int n, char *lookup) {
	if(n<=0) return -1;

	int low=0;
	int high=n-1;
	while(low<high) {
		int pos=(low+high)/2;
		int forward=pos;
		int backward=pos;
		bool bBack=false;

		while(forward<n && !strlen(input[forward])) {
			forward++;
		}
		if (forward==n) {
			//backward
			bBack=true;
		} else {
			int res=strcmp(input[forward], lookup);
			if(res==0) {
				return forward;
			} else if (res>0) {
				high=backward-1;
			} else {
				low=forward+1;
			}
		}

		if(bBack) {
			while(backward>=0 && !strlen(input[backward])) {
				backward--;
			}
			if(backward<0) {
				return -1;
			} else {
				int res=strcmp(input[backward], lookup);
				if(res==0) {
					return backward;
				} else if(res>0) {
					high=backward-1;
				} else {
					return -1;
				}
			}
		}
	}
	
	if(low==high) {
		int res=strcmp(input[low], lookup);
		if(res==0) {
			return low;
		}
	} 
	return -1; 
}


int main(int argc, char *argv[]) {
	char *input[]={"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
	char *lookup="atcar";
	int n=sizeof(input)/sizeof(lookup);
	cout<<LookUp(input, n, lookup)<<endl;
	return 0;
}